Search for: All records

We propose a new formula for the entropy of a dynamical black hole—valid to leading order for perturbations off of a stationary black hole background—in an arbitrary classical diffeomorphism covariant Lagrangian theory of gravity in $n$dimensions. In stationary eras, this formula agrees with the usual Noether charge formula, but in nonstationary eras, we obtain a nontrivial correction term. In particular, in general relativity, our formula for the entropy of a dynamical black hole differs from the standard Bekenstein-Hawking formula $A/4$by a term involving the integral of the expansion of the null generators of the horizon. We show that, to leading perturbative order, our dynamical entropy in general relativity is equal to $1/4$of the area of the apparent horizon. Our formula for entropy in a general theory of gravity is obtained from the requirement that a “local physical process version” of the first law of black hole thermodynamics hold for perturbations of a stationary black hole. It follows immediately that for first order perturbations sourced by external matter that satisfies the null energy condition, our entropy obeys the second law of black hole thermodynamics. For vacuum perturbations, the leading-order change in entropy occurs at second order in perturbation theory, and the second law is obeyed at leading order if and only if the modified canonical energy flux is positive (as is the case in general relativity but presumably would not hold in more general theories of gravity). Our formula for the entropy of a dynamical black hole differs from a formula proposed independently by Dong and by Wall. We obtain the general relationship between their formula and ours. We then consider the generalized second law in semiclassical gravity for first order perturbations of a stationary black hole. We show that the validity of the quantum null energy condition (QNEC) on a Killing horizon is equivalent to the generalized second law using our notion of black hole entropy but using a modified notion of von Neumann entropy for matter. On the other hand, the generalized second law for the Dong-Wall entropy is equivalent to an integrated version of QNEC, using the unmodified von Neumann entropy for the entropy of matter. Published by the American Physical Society2024 

Finding the connected components of a graph is a fundamental problem with uses throughout computer science and engineering. The task of computing connected components becomes more difficult when graphs are very large, or when they are dynamic, meaning the edge set changes over time subject to a stream of edge insertions and deletions. A natural approach to computing the connected components problem on a large, dynamic graph stream is to buy enough RAM to store the entire graph. However, the requirement that the graph fit in RAM is an inherent limitation of this approach and is prohibitive for very large graphs. Thus, there is an unmet need for systems that can process dense dynamic graphs, especially when those graphs are larger than available RAM. We present a new high-performance streaming graph-processing system for computing the connected components of a graph. This system, which we callGraphZeppelin, uses new linear sketching data structures (CubeSketch) to solve the streaming connected components problem and as a result requires space asymptotically smaller than the space required for a lossless representation of the graph.GraphZeppelinis optimized for massive dense graphs:GraphZeppelincan process millions of edge updates (both insertions and deletions) per second, even when the underlying graph is far too large to fit in available RAM. As a resultGraphZeppelinvastly increases the scale of graphs that can be processed. 

Finding the connected components of a graph is a fundamental prob- lem with uses throughout computer science and engineering. The task of computing connected components becomes more difficult when graphs are very large, or when they are dynamic, meaning the edge set changes over time subject to a stream of edge inser- tions and deletions. A natural approach to computing the connected components on a large, dynamic graph stream is to buy enough RAM to store the entire graph. However, the requirement that the graph fit in RAM is prohibitive for very large graphs. Thus, there is an unmet need for systems that can process dense dynamic graphs, especially when those graphs are larger than available RAM. We present a new high-performance streaming graph-processing system for computing the connected components of a graph. This system, which we call GraphZeppelin, uses new linear sketching data structures (CubeSketch) to solve the streaming connected components problem and as a result requires space asymptotically smaller than the space required for a lossless representation of the graph. GraphZeppelin is optimized for massive dense graphs: GraphZeppelin can process millions of edge updates (both inser- tions and deletions) per second, even when the underlying graph is far too large to fit in available RAM. As a result GraphZeppelin vastly increases the scale of graphs that can be processed.